One important problem in integrated circuit (IC) design is the minimization of the delay in the circuits. In ICs, Boolean circuits comprise trees to carry out certain Boolean functions. Typically, the Boolean circuits are created from a library of Boolean elements such as two-input AND and OR elements (cells) and NOT (inverter) elements or cells. The delay of Boolean circuits can ordinarily be minimized by minimizing the depth of the Boolean circuit.
The maximal number of cells that lie on any path from any input of a Boolean circuit to the output of the Boolean circuit is called a depth of a Boolean circuit. Each cell along the path adds one to the depth of the circuit. Thus, a tree or subtree having a path containing eight cells has a depth of 8. The delay of a Boolean circuit increases with its depth.
Considerable attention has been given to minimizing depth of Boolean circuits. Much of the attention has been directed at certain classes of Boolean functions (such as comparators, adders, subtractors, multipliers, etc), and to the development of techniques that allow fabricating Boolean circuits with small depth and small number of cells. In the present case, consideration is given to the special classes of Boolean circuits that perform the following functions:f0(x1, x2, . . . , xn)=x1(x2(x3(x4( . . . ))))f1(x1, x2, . . . , xn)=x1(x2(x3(x4( . . . )))).
The above functions are important because they are included in many arithmetic operations, such as addition, subtraction, and comparison. A fast hardware evaluation of these functions has been developed based on the presumption that all inputs x1, x2, . . . , xn of functions f0 and f1 have the same arrival depth when functions f0 and f1 are a part of adders and comparators.
Functions f0 and f1 are used in several methods of synthesis Boolean circuits other than special arithmetical operations, for example a Boolean function y determined by the RTL-Verilog code:                y=0;        if (A1) y=1;        if (A2) y=0;        if (A3) y=1;        if (A4) y=0;        if (A5) y=1;        . . .        if (An) y=0.It is clear that y=ƒ1({tilde under (A)}1, An-1, . . . , A1). Consequently, functions f0 and f1 can be used during the synthesis of Boolean circuits to evaluate Boolean functions determined by some programming languages.        
Variables A1, A2, . . . , An can be either single variables or comprehensive expressions that are evaluated by different Boolean circuits. These variables often have the different arrival depths. Because the values of variables A1, A2, . . . , An are evaluated by the different Boolean circuits whose depths are optimized separate from each other, a need exists for a more universal method of rapid reduction of the depth of functions f0 and f1 for various sets of arrival depths of inputs A1, A2, . . . , An.